package first.codeTop.alibaba;

/**
 * @ClassName LC39
 * @description:
 * @author: 荣燊
 * @create: 2021-10-18 20:01
 **/
public class LC39 {
    // 数组中出现次数超过一半的数字
    public static void main(String[] args) {
        int[] nums1 = {1, 2, 3, 2, 2, 2, 5, 4, 2};
        int[] nums2 = {2, 2, 1, 1, 1, 2, 2};
        System.out.println(majorityElement(nums2));
    }

    // 摩尔投票法
    public static int majorityElement(int[] nums) {
        int moreCount = nums[0];
        int count = 1;
        for (int i=1; i<nums.length; i++) {
            if (count == 0) {
                moreCount = nums[i];
                count++;
                continue;
            }
            if (nums[i] != moreCount) {
                count--;
            } else {
                count++;
            }
        }
        return moreCount;
    }
}
